package leetcode_41_60;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;

import static java.lang.Math.*;

public class merge_56 {
    /**
     * 合并所有重叠的区间，并返回 一个不重叠的区间数组
     * 该数组需恰好覆盖输入中的所有区间 。
     * 输入: [[1,4],[4,5]]
     * 输出: [[1,5]]
     *
     * 最后用了大佬思路
     * 7ms
     * 81%
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval : intervals) {
            //第一次遍历：{1,3}--interval[0] = 1, 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
            if (idx == -1 || interval[0] > res[idx][1]) {
                //res[0]=[{1,3}]
                res[++idx] = interval;  //当前区间与结果数组最后一个区间无重叠，把当前区间加入结果中
            } else {
                //第二次遍历：[2,6]
                //当前区间的起始位置 < 结果数组中最后区间的终止位置， 2 < 3
                //比较当前结果集中右边值是否重合(interval[1]=6,res[idx][1]=3)
                //将较大的值作为新的边界值  [1,6]
                res[idx][1] = max(res[idx][1], interval[1]);
            }
        }
        //截取有效数组，去掉末尾未使用的空数组
        return Arrays.copyOf(res, idx + 1);
    }
}
